Representation of binary arithmetic operands in two's complement format is useful in many data processing applications. For example, if the precision of the operand is 8 bits, then the values of the operand will range from −128 to 127. Such a two's complement representation is often illustrated by a circle as shown in FIG. 1.
The two's complement representation has been used, for example, in the alpha and beta state metric calculation blocks of conventional turbo decoders. The two's complement representation is useful in the alpha and beta state metric calculations because the value of these metrics increases during each iteration of the trellis. When, for example, a binary operand reaches the maximum positive value which can be represented by a specific number of bits, a further increase in the magnitude of that operand will cause its value to wrap around the circle to the most negative number, for example, −128 in an 8 bit representation. As a specific example, adding 2 to 127 causes an overflow to −127 as shown below:
                              127          ⁢                                                                                                                                                        0111                    1111                                      2          ⁢                                                                                                                                                        0000                    0010                                      129          ⁢                                                                                                                                                        1000                    0001                                                  -            127                    ⁢                                                                                                                                                        1000                    0001               This wrap-around operation associated with two's complement representation advantageously normalizes operands automatically, without requiring additional normalization circuitry.
Viterbi decoders have trellis properties that are similar to turbo decoders, and part of the Viterbi decoder is comparable with either the beta or alpha state metric blocks of the turbo decoder, so two's complement representation is also conventionally used in some Viterbi decoders for similar normalization purposes. The two's complement format can be useful in many data processing applications, such as those where operand normalization is needed.
Referring again to the circle of FIG. 1, and considering the example of a turbo decoder, the two's complement technique works for the alpha and beta state metric blocks, as long as all metric values for each of the turbo decoder states reside in one-half (two adjacent quarters) of the circle for each recursive operation of the turbo decoder. If the alpha or beta state metric values for any state of the turbo decoder reside in more than two adjacent quarters of the circle, then it is not possible to determine overflows. This situation of having alpha or beta state metric values for a given state residing in more than two adjacent quarters of the circle could happen if there are not enough bits for the operands. Therefore, conventional turbo and Viterbi decoders that use two's complement normalization typically ensure that, for each iteration of the turbo decoder trellis, there are enough bits available to prevent the alpha and beta state metrics from residing in more than two adjacent quarters of the circle.
Although the use of two's complement representation can be advantageous in binary arithmetic calculations, nevertheless the present invention has discovered that problems can arise when binary arithmetic operands cross the maximum positive/maximum negative value boundary. In order to avoid these problems, the present invention provides a quadrant shifting technique wherein the values of the binary operands are adjusted (relocated on the circle) appropriately to avoid arithmetic operations that cross the maximum positive/maximum negative value boundary. Advantageously, the quadrant shifting technique can also be designed to reduce the number of bits required for two's complement representation of the operands.